Description of the 1997 problem, with pointers.

A KID GOES TO SCHOOL ...
A WHIZZKID SENDS HIS PARENTS AND WINS Dfl.5,000.-

School is open tonight. The teachers don't talk to the students but to their parents. The students are eagerly waiting for their parents to come back home. But nobody knows at what time they will return, because the parents are wandering along the corridors and the teachers are impatiently waiting for the next parents to see. Who is responsible for the timetable? Well, you are!

WHAT SHOULD YOU DO?

You must construct a timetable for the parents' evening. There are two groups of people: 20 parents and 15 teachers. A total of 197 conversations has to be scheduled. A teacher can see only one parent at a time, and a parent can see only one teacher at a time. The parents' evening starts at 16:00 hours and must be completed as early as possible. The 15 teachers are denoted by A, B, C, D, E, F, G, H, J, K, L, M, N, P, and R. The parents are denoted by numbers ranging from 1 up to 20.
Parents have expressed their conversation requests by means of capital-number codes. D15 indicates a request for a conversation with teacher D that lasts 15 minutes. The requests are given by sequences. The sequence (D15)(A6) denotes that the parent first wants to see teacher D for 15 minutes, and next teacher A for 6 minutes. A sequence of character-number combinations in between brackets denotes that the sequence in which the conversations take place doesn't matter. Thus, (D15,A6) denotes that teacher D can be visited either before or after A. A listing of the conversation requests is given in the attached local gif file and also in our local numerical data file (text-file). You don't have to take the time needed to go from one teacher to the other into account; so the conversations can follow each other directly in time.

YOUR SOLUTION

The timetable you need to construct must indicate for each parent the sequence of teachers that he is going to see during the evening, together with the starting times of the conversations. The solution should fit in the solution form. An alternative timetable, indicating for each teacher the sequence of parents, together with the starting times, is also accepted.

Mrs. Hosman for example has issued the following request: (D15)(A6,B8,G10). Then the sequence D16:30, B16:45, G17:20, A17:30 indicates that she will see teacher D at 16:30, teacher B at 16:45, teacher G at 17:20, and finally teacher A at 17:30. She can go home at 17:36.

Your solution should be a timetable that meets all the parents' conversation requests and has minimum length. The parents' evening starts at 16:00 and ends when the last parent can go home. You should indicate this point in time on the form. You also should try to minimize the run time of the parents.

The jury collects all submitted solutions. It first checks the correctness of a solution. Next the correct solutions are ordered with respect to their lengths. If solutions have equal lengths, the total run time of the parents is taken into account. This is the sum of the run times of the individual parents, where the run time of a parent is the length of the period from the moment he starts his first conversation until he can go home.

WHAT ARE THE PRIZES?

CMG has donated a number of considerable cash prizes. The general category has ten prizes: Dfl. 5,000.-, Dfl. 4,000.-, Dfl. 3,000.-, and Dfl. 2,000.-, and six prizes of Dfl. 1,000.-. There are three additional prizes for the best high school student, the best high school class, and the best university student, respectively. Students that submit as member of their class are not allowed to submit individually. There is a category for professionals (those who are professionally involved in mathematics or computer science) with three prizes: Dfl. 5,000.-, Dfl. 2,500.-, and Dfl. 1,000.-. Participation is subject to rules described (in Dutch) in the game regulations. In particular they say that solutions resulting from a joint effort may be submitted, but only under the condition that they be marked as such, and contain the names of those involved.

Submissions should arrive before October 21, 1997, at

Lubbers en Dijk Notarissen
P.O. Box 53040
1007 RA Amsterdam
The Netherlands

CMG Nederland B.V.
Department for Communication
P.O. Box 159
1180 AD Amstelveen
The Netherlands
+ 3120 50 33 000

This page was modified last on: December 23, 1997,
by Cor Hurkens (wscor@win.tue.nl)